import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
         int n = scan.nextInt() ;
         int v = scan.nextInt() ;
         int[][] nums = new int[n+1][2] ; 
         for(int i=1 ; i<=n ; i ++){
            nums[i][0] = scan.nextInt() ;
            nums[i][1] = scan.nextInt() ;
         }
         int[][] dp = new int[n+1][v+1] ; 
         for(int i=1 ; i<= n ; i ++){
            for(int j=1 ; j<=v ; j ++){
              dp[i][j] = dp[i-1][j] ; 
              if(j>=nums[i][0]){
                dp[i][j] = Math.max(dp[i][j] , dp[i][j-nums[i][0]]+nums[i][1]) ; 
              }
            }
         }
       System.out.println(dp[n][v]);
        dp = new int[n+1][v+1] ; 
       
        for(int i=1 ; i<=v ; i++) dp[0][i] = -1 ;

        for(int i=1 ; i<=n ; i ++){
            for(int j=1 ; j<=v ; j ++){
                dp[i][j] = dp[i-1][j] ; 
                if(j>= nums[i][0] && dp[i][j-nums[i][0]] != -1){
                    dp[i][j] = Math.max(dp[i][j] , dp[i][j-nums[i][0]] + nums[i][1]) ; 
                }
            }
        }
      System.out.println(dp[n][v]>0?dp[n][v]:0);

    }
}